package 省份数量;

import java.util.LinkedList;

/**
 * 省份数量 图算法
 * <p>
 * 有n个城市，其中一些彼此相连，另一些没有相连。如果城市a与城市b直接相连，且城市b与城市c直接相连，那城市a与城市c间接相连。
 * 省份是一组直接或间接相连的城市，组内不含其它没有相连的城市。
 * 给你一个n x n的矩阵isConnected，其中isConnected[i][j] = 1 表示第i个城市和第j个城市直接相连，而isConnected[i][j] = 0 表示 二者不直接相连。
 * 要求：返回矩阵中省份的数量。
 * <p>
 * 扩展：朋友圈问题，亲戚问题。
 */
public class Solution {
    public static void main(String[] args) {
        /*
            广度优先：先找到所有直接相连的城市，再找所有间接相连的城市
            深度优先：递归找到直接相连的城市
         */

        // 2
        int count = depthFirst(new int[][]{{1, 1, 0}, {1, 1, 0}, {0, 0, 1}});
        System.out.println("count = " + count);

        // 3
        count = depthFirst(new int[][]{{1, 0, 0}, {0, 1, 0}, {0, 0, 1}});
        System.out.println("count = " + count);

        // 2
        count = breadthFirst(new int[][]{{1, 1, 0}, {1, 1, 0}, {0, 0, 1}});
        System.out.println("count = " + count);

        // 3
        count = breadthFirst(new int[][]{{1, 0, 0}, {0, 1, 0}, {0, 0, 1}});
        System.out.println("count = " + count);

        // 2
        count = mergeFind(new int[][]{{1, 1, 0}, {1, 1, 0}, {0, 0, 1}});
        System.out.println("count = " + count);

        // 3
        count = mergeFind(new int[][]{{1, 0, 0}, {0, 1, 0}, {0, 0, 1}});
        System.out.println("count = " + count);

    }

    /**
     * 并查集-多叉树
     */
    private static int mergeFind(int[][] cityConnected) {

        // 每个城市看成一个节点，构建成一个tree
        /*
        index代表城市，array存储城市的根节点下标，数组下标和值一致时，表示一个根节点，即一个省份
        array: 0 1 1
        index: 0 1 2
         */

        int size = cityConnected.length;

        int[] head = new int[size];
        int[] level = new int[size];

        for (int i = 0; i < size; i++) {
            head[i] = i;
            level[i] = 1;
        }

        for (int i = 0; i < size; i++) {
            for (int j = i + 1; j < size; j++) {
                if (cityConnected[i][j] == 1) {
                    merge(i, j, head, level);
                }
            }
        }

        int provinces = 0;
        for (int i = 0; i < size; i++) {
            if (head[i] == i) {
                provinces++;
            }
        }
        return provinces;

    }

    private static void merge(int i, int j, int[] head, int[] level) {
        // 找i城市关联的根节点下标
        int x = findRoot(i, head);
        // 找j城市关联的根节点下标
        int y = findRoot(j, head);

        if (x == y) {
            // 同一个根节点，无需合并
            return;
        }

        // 层级小的合并到层级高的树中，以减少findRoot路径压缩时递归次数
        // 层级可选
        if (level[x] > level[y]) {
            head[y] = x;
            level[y]++;
        } else {
            head[x] = y;
            level[x]++;
        }
    }

    private static int findRoot(int i, int[] head) {

        if (head[i] == i) {
            return i;
        }

        // 各节点，进行路径压缩，直接指向根节点下标
        head[i] = findRoot(head[i], head);
        return head[i];
    }


    /**
     * 广度优先
     */
    private static int breadthFirst(int[][] cityConnected) {
        int size = cityConnected.length;
        int provinces = 0;
        boolean[] visited = new boolean[size];

        LinkedList<Integer> queue = new LinkedList<>();

        for (int i = 0; i < size; i++) {
            if (!visited[i]) {
                queue.offer(i);

                while (!queue.isEmpty()) {
                    int pop = queue.pop();
                    visited[pop] = true;

                    // 处理下一层
                    for (int j = 0; j < size; j++) {
                        if (cityConnected[i][j] == 1 && !visited[j]) {
                            queue.offer(j);
                        }
                    }
                }
                provinces++;
            }
        }
        return provinces;
    }

    /**
     * 深度优先
     * 时间复杂度 O(n*n)
     * 空间复杂度 O(n)
     */
    private static int depthFirst(int[][] cityConnected) {
        int size = cityConnected.length;
        int provinces = 0;
        boolean[] visited = new boolean[size];
        for (int i = 0; i < size; i++) {
            if (!visited[i]) {
                dfs(i, cityConnected, visited, size);
                provinces++;
            }
        }
        return provinces;
    }

    private static void dfs(int i, int[][] cityConnected, boolean[] visited, int size) {
        for (int j = 0; j < size; j++) {
            if (cityConnected[i][j] == 1 && !visited[j]) {
                visited[j] = true;
                dfs(j, cityConnected, visited, size);
            }
        }
    }


}
